Today it is common to use some kind of navigation system when preparing a journey as well as during a journey (e.g. by foot, by bike or by car) from one location to another. A navigation system may e.g. be a web mapping service with road route planning functionality, or a positioning system such as GPS. Such navigation systems are capable of calculating route suggestions which then may be followed to reach a desired destination.
To accomplish this, a navigation system may use coordinate data for a plurality of geographical locations as well as data relating to how these locations are connected. Typically, this data may be stored in a graph data structure wherein the nodes represent the geographical locations and the edges or links connecting the nodes represent how these locations are connected. For example, a link connecting two nodes may represent a road segment extending between the geographical locations represented by the nodes. Two connected nodes thus make up a route segment in the navigation system, which route segment may correspond to a road segment extending between the geographical locations. Longer routes may be formed from a plurality of consecutive and connected route segments in the graph.
Each route segment has an associated base quantity corresponding to a time for traversing a corresponding road segment at a given speed (e.g. a ratio of the length of the road segment over the legal speed limit along the road segment) or a distance of the corresponding road segment. The total base quantity for a complete route is the sum of the base quantities of the route segments making up the complete route.
Generally, the route suggested by a navigation system corresponds to the most efficient way of reaching the destination (e.g. in terms of distance or time). The most efficient route corresponds to the route having the smallest sum of base quantities. This route is commonly calculated using the Dijkstra graph-traversal algorithm or variants thereof.
The base quantity of a route segment is generally a predetermined quantity which does not reflect dynamic conditions along the corresponding road segment. In order to improve route suggestions and travel time estimates in view of dynamic conditions some navigation systems take traffic flow along the route segments into account. The traffic flow may be a predicted traffic flow or a real-time traffic flow. Some navigation systems also take incident information into account. The incident information is commonly reported to a navigation system by a third-party reporting facility. For example, if an incident occurs along a road segment corresponding to a route segment the facility may report an “incident number” indicative of the severity of the incident. The incident number may e.g. be an integer on a standardized scale (e.g. 1 and 5) where a small integer may indicate a small incident and large integer may indicate a major incident. Different standardizations and different grading of incidents may be used in different environments and countries.
When both traffic flow and incident information is available in a prior art navigation system, their delaying effects on a route segment are estimated separately from each other. An updated quantity of the affected route segment is then determined as the sum of the base quantity of the route segment, an estimated delaying effect of the traffic flow and an estimated delaying effect of the incident number.
Accordingly, it would be desirable to provide an improved way of calculating quantities for a route segment compared to the prior art. Specifically, it would be desirable to provide a more accurate way for calculating quantities for a route segment in view of more than one road condition.